W08. Emergence 01
Today, we really start to dig into complexity science 101: automata. If you've taken a discrete math course, you've probably already seen finite state machines (FSMs) a.k.a. deterministic finite state automata (DFAs).
Automata are a good model for the robot, because it is an automaton. But also, they are a good model for intelligent emergence, that is, when intelligent behaviour seems to emerge out of unintelligent actions. Further, some automata demonstrate a further property of complex systems called chaos.
Pre-readings and Videos
The following readings outline automata and give examples of chaotic systems.
Langton's Ant
This is a simulation of Langton's Ant. Langton's Ant is a simple automaton that produces chaotic and therefore "unpredictable" behaviour, yet it is deterministic.
Cellular Automata Rules
An enumeration (and index) of cellular automata based on a structured rule pattern can exhibit behaviour that is both chaotic and complex. In fact, certain cellular automata are Turing-complete, that is, they can compute.
Sphex Wasp and Determinism
The Sphex Wasp has often been cited as an example of a natural automaton. But is it true? Is intelligence even possible without memory?
On the other hand, very intelligent systems with impairment may also exhibit repetition.
Summary of the Day
- Activity. Automata Explorer.
- Activity. Langton's Ant.
- Class notes. Available here
Learning Goals
- Be able to describe and simulate Langton's Ant and Conway's Game of Life on paper.
- Be able to characterize a system in terms of chaos and predictability.
- Design a simple automaton to achieve a goal.